快速傅里叶变换

Fast Fourier Transform FFT
是一种高效计算离散傅里叶变换（DFT）及其逆变换的算法。FFT 算法显著减少了执行 DFT 所需的乘法和加法次数，从而提高了计算效率。

FFT 的基本原理

FFT 算法基于 DFT 的递归分解，将 DFT 分解为多个较小的 DFT 问题，然后递归地解决这些较小的问题。这种分解利用了“蝶形操作”（butterfly operation），它是一种特定的计算模式，可以减少所需的乘法次数。

FFT 的主要算法

Cooley-Tukey 算法：这是最常用的 FFT 算法，它使用分而治之的策略，将 DFT 分解成较小的 DFT，通常是偶数点和奇数点的 DFT。
Good-Thomas 算法：这种算法适用于处理矩形数据集，例如二维 FFT。
Rader 算法：当输入数据是周期性的或已知具有某些对称性质时，Rader 算法可以减少计算量。
Swinney 算法：这种算法适用于处理具有对称性的信号。

FFT 的计算复杂度

FFT 算法将 DFT 的计算复杂度从 ( O (N^2) ) 降低到 ( O (N \log N) )，其中 ( N ) 是输入数据的长度。这意味着对于长度为 ( N ) 的序列，FFT 算法的计算时间与 ( N ) 成线性对数关系，而不是与 ( N^2 ) 成二次方关系。

FFT 的应用

信号处理：FFT 是信号分析中的核心工具，用于频谱分析、滤波和信号检测。
图像处理：在图像压缩和图像分析中，FFT 用于快速变换到频域。
音频处理：在音频分析和处理中，FFT 用于分析音频信号的频率成分。
数据压缩：FFT 用于数据压缩算法中，以减少数据的存储和传输需求。
量子计算：在量子算法中，FFT 是量子傅里叶变换的基础。
机器学习：在某些机器学习算法中，FFT 用于快速计算卷积和相关性。

FFT 算法的高效性使其成为现代计算中不可或缺的一部分，特别是在需要处理大量数据的应用中。

AI 结构化补充（2026-05-02）

Fast Fourier Transform FFT
是一种高效计算离散傅里叶变换（DFT）及其逆变换的算法。若把 DFT 写成 Fourier 矩阵乘法 $y = F_{n} c$ ，直接相乘需要 $n^{2}$ 次量级的乘法；FFT 利用单位根的递归结构，把核心复乘数降到

\frac{1}{2} n \log_{2} n

量级。

FFT 的基本原理

本页采用正号单位根约定

w_{n} = e^{2 π i / n}, (F_{n})_{j, k} = w_{n}^{j k}, j, k = 0, \dots, n - 1.

若采用工程软件中常见的负号单位根，得到的是共轭 Fourier 矩阵；递归结构相同，只是旋转因子取共轭。

FFT 的核心不是改变 DFT 的定义，而是把同一个矩阵乘法重新因式分解。对 $n = 2^{ℓ}$ ，每一步把长度 $n$ 的问题拆成两个长度 $m = n / 2$ 的问题，再用少量旋转因子合并。这个 radix-2 分解通常称为 Cooley-Tukey 算法，思想也可追溯到 Gauss 对三角插值计算的分解。

定义约定与适用边界

DFT 本身由长度 $n$ 、单位根符号和归一化约定唯一决定；FFT 只是计算同一个线性变换的快速算法，不是近似算法。常见归一化有三种：正变换不归一、逆变换除以 $n$ ；正变换除以 $n$ ；或正逆都除以 $\sqrt{n}$ 。只有最后一种使 Fourier 矩阵本身成为酉矩阵。

radix-2 FFT 要求 $n = 2^{ℓ}$ 。若 $n$ 不是二的幂，仍可用混合基 Cooley-Tukey、Rader、Bluestein 等分解处理；若 $n$ 是素数，不能直接做偶奇递归。补零可以把数据嵌入更长的 DFT 以便使用高效长度，但它改变的是采样频率网格，不等同于原长度 DFT 的值。

输入可以是实数或复数。实输入的 DFT 满足共轭对称

y_{n - j} = \overset{―}{y_{j}},

所以实际软件常用 real FFT 只计算一半频谱；复输入则没有这个对称性。

FFT 的主要算法

Cooley-Tukey 算法：本页主线采用 radix-2 情形，把输入按偶数下标和奇数下标分成两个半长 DFT，再通过蝶形合并得到完整输出。
Good-Thomas、Rader 等变体：这些算法处理不同长度分解或素数长度等情形；在这里只作为 FFT 家族的补充背景，不作为本页推导主线。

一步偶奇分解

令 $m = n / 2$ ，把输入向量按下标奇偶拆成

c^{'} = (c_{0}, c_{2}, \dots, c_{n - 2})^{T}, c^{″} = (c_{1}, c_{3}, \dots, c_{n - 1})^{T} .

先计算两个半长 Fourier 变换

y^{'} = F_{m} c^{'}, y^{″} = F_{m} c^{″} .

那么完整输出 $y = F_{n} c$ 的前半和后半由

y_{j} = y_{j}^{'} + w_{n}^{j} y_{j}^{″}, y_{j + m} = y_{j}^{'} - w_{n}^{j} y_{j}^{″}, j = 0, \dots, m - 1

给出。

推导直接来自把求和按偶数项与奇数项分开：

y_{j} = \sum_{k = 0}^{n - 1} w_{n}^{j k} c_{k} = \sum_{r = 0}^{m - 1} w_{n}^{2 j r} c_{2 r} + w_{n}^{j} \sum_{r = 0}^{m - 1} w_{n}^{2 j r} c_{2 r + 1} .

关键关系是

w_{n}^{2} = e^{2 π i / m} = w_{m},

因此两个求和正是 $F_{m} c^{'}$ 与 $F_{m} c^{″}$ 。对后半输出 $y_{j + m}$ ，偶数项仍给出同一个 $y_{j}^{'}$ ，奇数项多出因子

w_{n}^{m} = e^{π i} = - 1,

所以合并公式中的第二项变为负号。这就是蝶形合并的代数来源。

Fourier 矩阵分解形式

把上面的偶奇拆分写成矩阵乘积，令 $P_{eo}$ 表示 even-odd permutation，把输入重排为

(c_{0}, c_{2}, \dots, c_{n - 2}, c_{1}, c_{3}, \dots, c_{n - 1})^{T} .

若 $w^{n} = 1$ 且 $F_{n}$ 的条目为 $(F_{n})_{j, k} = w^{j k}$ ，则

F_{n} = [\begin{matrix} I & D \\ I & - D \end{matrix}] [\begin{matrix} F_{n / 2} & 0 \\ 0 & F_{n / 2} \end{matrix}] P_{eo},

其中

D = diag (1, w, w^{2}, \dots, w^{n / 2 - 1}) .

第一因子完成蝶形合并，第二因子执行两个半长 Fourier 变换，第三因子只改变输入顺序。未归一化 Fourier 矩阵的列正交性可写成

F_{n}^{*} F_{n} = n I,

等价地，归一化矩阵 $F_{n} / \sqrt{n}$ 是酉矩阵。

当 $n = 2^{ℓ}$ 时，这个分解可递归 $ℓ$ 层。每一层只有 $n / 2$ 个来自对角矩阵 $D$ 的核心复乘法，因此计算 $F_{n} x$ 的核心乘法数约为

\frac{1}{2} n ℓ = \frac{1}{2} n \log_{2} n .

$F_{4}$ 的三因子分解

四点情形已经包含 FFT 的完整结构。设 $w_{4} = i$ ，则

F_{4} = (\begin{matrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & i \\ 1 & 0 & - 1 & 0 \\ 0 & 1 & 0 & - i \end{matrix}) (\begin{matrix} 1 & 1 & 0 & 0 \\ 1 & - 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & - 1 \end{matrix}) (\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{matrix}) .

最右侧矩阵是 even-odd permutation，把 $(c_{0}, c_{1}, c_{2}, c_{3})^{T}$ 变成 $(c_{0}, c_{2}, c_{1}, c_{3})^{T}$ 。中间矩阵是两个 $F_{2}$ 的块对角和，分别计算偶项与奇项的二点变换。最左侧矩阵执行蝶形合并：用 $1, i$ 乘奇项半变换，并与偶项半变换相加或相减，得到 $y_{0}, y_{1}, y_{2}, y_{3}$ 。

FFT 的计算复杂度

直接计算 $F_{n} c$ 需要 $n^{2}$ 次量级的乘法，因为 $F_{n}$ 有 $n^{2}$ 个非零元素。FFT 的一次拆分只把工作量近似减半还不够，真正的节省来自继续递归：

F_{n} \to 2 F_{n / 2} \to 4 F_{n / 4} \to \dots \to n F_{1} .

若 $n = 2^{ℓ}$ ，共有 $ℓ = \log_{2} n$ 层。每一层的蝶形合并需要 $n / 2$ 个旋转因子乘法，因此核心复乘数为

\frac{1}{2} n ℓ = \frac{1}{2} n \log_{2} n .

例如 $n = 1024 = 2^{10}$ 时，直接乘法约为

1024^{2} = 1 048 576

次，约一百万次；FFT 的旋转因子乘法为

\frac{1}{2} \cdot 1024 \cdot 10 = 5120

次，节省约两个数量级。

位反转顺序

每一层都先把偶数下标放在奇数下标之前。把所有层的 even-odd permutation 合起来，会得到二进制位反转顺序。以 $n = 8$ 为例，把下标写成三位二进制并反转：

\begin{array}{ccc} 原下标 & 二进制 & 反转后 \\ 0 & 000 & 0 \\ 1 & 001 & 4 \\ 2 & 010 & 2 \\ 3 & 011 & 6 \\ 4 & 100 & 1 \\ 5 & 101 & 5 \\ 6 & 110 & 3 \\ 7 & 111 & 7 \end{array}

所以

0, 1, 2, 3, 4, 5, 6, 7 ⟼ 0, 4, 2, 6, 1, 5, 3, 7.

许多迭代式 FFT 实现先按这个顺序重排输入，再逐层执行蝶形合并。

线性代数解释与唯一性

从矩阵分解角度看，FFT 把稠密 Fourier 矩阵写成置换矩阵、块对角小 Fourier 矩阵、对角旋转因子和蝶形矩阵的乘积。每个因子都很稀疏或结构化，因此整体乘法比直接使用 $F_{n}$ 便宜得多。归一化后，整个变换保持二范数：

{‖ \frac{1}{\sqrt{n}} F_{n} x ‖}_{2} = ∥ x ∥_{2},

这就是 Parseval 恒等式的矩阵形式。

FFT 分解不唯一。可以按时间抽取或频率抽取组织蝶形，可以选择不同 radix，也可以把同一组旋转因子分配到不同层。只要符号和归一化一致，这些算法计算的是同一个 DFT；差异主要体现在内存访问顺序、常数因子、并行性和舍入误差分布。

边界情形中， $n = 1$ 时 DFT 是恒等变换，不需要蝶形； $n = 2$ 时只有一次加减法。数值上，FFT 的误差通常随层数增长，约与 $\log n$ 相关，而直接乘法有更多运算但舍入路径不同。因此在高精度或病态频谱问题中，仍要明确归一化、缩放和浮点精度。

FFT 的应用

信号处理：FFT 是信号分析中的核心工具，用于频谱分析、滤波和信号检测。
图像处理：在图像压缩和图像分析中，FFT 用于快速变换到频域。
音频处理：在音频分析和处理中，FFT 用于分析音频信号的频率成分。
数据压缩：FFT 用于数据压缩算法中，以减少数据的存储和传输需求。
量子计算：在量子算法中，FFT 是量子傅里叶变换的基础。
机器学习：在某些机器学习算法中，FFT 用于快速计算卷积和相关性。

FFT 算法的高效性使其成为现代计算中不可或缺的一部分，特别是在需要处理大量数据的应用中。

FFT 的基本原理

FFT 的主要算法

FFT 的计算复杂度

FFT 的应用

AI 结构化补充（2026-05-02）

FFT 的基本原理

定义约定与适用边界

FFT 的主要算法

一步偶奇分解

Fourier 矩阵分解形式

F4 的三因子分解

FFT 的计算复杂度

位反转顺序

线性代数解释与唯一性

FFT 的应用

$F_{4}$ 的三因子分解